package top.humbleyuan.sortmethod;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @Author HumbleYuan
 * @Date 2020/3/18 22:07
 * @Des 归并
 */
public class Merge {
    public static void main(String[] args) {
        int[] nums = {6,2,45,7,89};
        int[] sortedNums =  partition(nums);
        System.out.println(Arrays.toString(sortedNums));
    }

    public static int[] partition(int[] nums) {
        if(nums.length < 2) {
            return nums;
        }

        int[] left = Arrays.copyOfRange(nums,0,nums.length >> 1);
        int[] right = Arrays.copyOfRange(nums, nums.length >> 1, nums.length);
        return mergeSort(partition(left), partition(right));
    }

    public static int[] mergeSort(int[] left, int[] right) {
        int[] temp = new int[left.length + right.length];
        int k = 0;

        int i = 0, j = 0;
        while(i < left.length || j < right.length) {
            if(i == left.length) {
                temp[k++] = right[j++];
                continue;
            }
            if(j == right.length) {
                temp[k++] = left[i++];
                continue;
            }

            if(left[i] < right[j]) {
                temp[k++] = left[i++];
            }else {
                temp[k++] = right[j++];
            }
        }
        return temp;
    }
}
